#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<string>

using namespace std;

void dfs(int n, const vector<bool>& sta1, vector<bool>& sta2, long long& res, int modulo, int k)
{
    if (n >= sta1.size())
    {
        int cnt = 0;
        for (int i = 0; i < sta1.size(); i++)
        {
            if (sta2[i])
            {
                if (sta1[i])
                    cnt++;
            }
            else
                break;
        }
        if (cnt % modulo == k)
            res++;
        return;
    }
    sta2[n] = true;
    dfs(n + 1, sta1, sta2, res, modulo, k);
    sta2[n] = false;
    dfs(n + 1, sta1, sta2, res, modulo, k);
}

//long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
//    vector<bool> sta1(nums.size());
//    for (int i = 0; i < nums.size(); i++)
//    {
//        if (nums[i] % modulo == k)
//            sta1[i] = true;
//    }
//    long long res = 0;
//    vector<bool> sta2(nums.size());
//    dfs(0, sta1, sta2, res, modulo, k);
//    return res;
//}

long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
    vector<int> count(nums.size() + 1, 0);
    for (int i = 1; i <= nums.size(); i++)
    {
        if (nums[i - 1] % modulo == k)
            count[i] = 1;
        count[i] += count[i - 1];
    }
    long long res = 0;
    for (int i = 1; i <= nums.size(); i++)
    {
        for (int j = i; j <= nums.size(); j++)
        {
            int cnt = count[j] - count[i - 1];
            if (cnt % modulo == k)
                res++;
        }
    }
    return res;
}

int main()
{
    vector<int> v = { 3,1,9,6 };
    cout << countInterestingSubarrays(v, 3, 0);
	return 0;
}